package P200;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author DJ同学
 * @Date 2021/2/10 22:47
 * @Version 1.0
 * @Name 岛屿数量
 * @Problem https://leetcode-cn.com/problems/number-of-islands/
 * @idea 并查集
 */
public class Solution {

    @Test
    public void test(){
        char[][] grid={{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}} ;
        System.out.println(numIslands(grid));
    }
    int pre[];
    public int numIslands(char[][] grid) {
        pre = new int[grid.length*grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    pre[i*grid[0].length+j]=i*grid[0].length+j;
                }else{
                    pre[i*grid[0].length+j]=-1;
                }
            }
        }
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1') {
                    grid[i][j]='0';
                    if(i-1>=0&&grid[i-1][j]=='1') join(i*grid[0].length+j,(i-1)*grid[0].length+j);
                    if(i+1<grid.length&&grid[i+1][j]=='1') join(i*grid[0].length+j,(i+1)*grid[0].length+j);
                    if(j-1>=0&&grid[i][j-1]=='1') join(i*grid[0].length+j,i*grid[0].length+j-1);
                    if(j+1<grid[0].length&&grid[i][j+1]=='1') join(i*grid[0].length+j,i*grid[0].length+j+1);
                }
            }
        }
        int cnt=0;
        for(int i=0;i<pre.length;i++){
            System.out.println(pre[i]);
            if(pre[i]==i){
                cnt++;
            }
        }
        return cnt++;
    }
    int find(int x){
        while(x!=pre[x]){
            x=pre[x];
        }
        return x;
    }
    void join(int i,int j){
        int prei=find(i);
        int prej=find(j);
        pre[prei]=prej;
    }

}
